package cn.com.fattiger.framework;

/**
 * 
 * InsertSort
 * 
 * @author fattiger.xiaoyang
 * @date 2016/12/14
 * @qqGroup 454655009
 * @desc 插入排序 
 * 			外层for循环 从数组索引第一位开始遍历 （默认索引从0开始） 
 * 			内层while循环 循环变量当前遍历索引减一
 *       	判断索引之前的排完序的所有元素与外层循环的变量数据比较
 *       	如果大于外层变量则进行置换 
 *       	直到循环结束（j<0&&a[j]>val 只要一个不满足循环就结束） 把外层因子插入置换后的空位 
 *       	为什么是j+1?循环对j做了--操作 +1后 正好是没减之前的位置
 */
public class InsertSort {

	public static void main(String[] args) {
		int a[] = { 3, 2, 5, 1, 2, 3, 8 };
		sort(a);
		for (int m : a) {
			System.out.print(m);
		}
	}

	public static void sort(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int val = a[i];
			int j = i - 1;
			while (j >= 0 && a[j] > val) {
				a[j + 1] = a[j];
				j--;
			}
			a[j + 1] = val;
		}
	}

	public static void sort1(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int j = i - 1;
			int val = a[i];
			while (j >= 0 && a[j] > val) {
				a[j + 1] = a[j];
				j--;
			}
			a[j + 1] = val;
		}
	}

	public static void sort3(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int val = a[i];
			int j = i - 1;
			while (j > 0 && a[j] > val) {
				a[j + 1] = a[j];
				j--;
			}
			a[j + 1] = val;
		}
	}
}
